package com.rui.study.algorithm.SORT_5_快速排序_分治思想_分区函数;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-11-08 17:24
 **/
public class QuickSort {

    /**
     * 快速排序：选取某个值pivot，比pivot小的放到小区间，比pivot大的分到大区间，一直分下去，直到区间内只有一个元素为止。
     * 最好时间复杂度：O(nlogn)
     * 最坏时间复杂度：O(n²)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param a
     */
    public static void sort(int[] a) {
        partition(a, 0, a.length-1);
    }

    private static void partition(int[] a, int start, int end) {
        if (end > start) {
            int pivot = (a[start] + a[(start+end)/2] + a[end]) / 3;
            int idx = start;
            for (int i=start; i<=end; i++) {
                int tmp = a[i];
                if (tmp > pivot) {
                    continue;
                } else {
                    a[i] = a[idx];
                    a[idx++] = tmp;
                }
            }
            // 小区间
            partition(a, start, idx-1);
            // 大区间
            partition(a, idx, end);
        }
    }
}
